package 力扣.中等;

import java.util.Arrays;
/*
* 给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。

示例 1:

输入: nums = [1, 5, 1, 1, 6, 4]
输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]
示例 2:

输入: nums = [1, 3, 2, 2, 3, 1]
输出: 一个可能的答案是 [2, 3, 1, 3, 1, 2]
* 重点：摆动排序 和把很多数 一组一组的数插入数组
摇摆排序：就是从中位数和最大数开始选择
   int i=0;
        int mid=n%2==0?n/2:(n/2+1);
        int high=n-1;
        for (; i <n/2; i++) {
            res[2*i]=nums[mid-i-1]; //从中位数开始
            res[2*i+1]=nums[high-i-1]; //从最大数开始
        }
        * if(n%2!=0) res[2*i]=nums[0];
        *
        * 最后一个if是为了防止数组的数量是奇数个 这样就剩下第一个没有排序

* */
public class 摆动排序 {
    class Solution {
        public void wiggleSort(int[] nums) {
            int len = nums.length;
            int[] bak = Arrays.copyOf(nums, len);
            Arrays.sort(bak);
            int sStart = (len+1)/2;
            int bStart = len - 1;
            sStart--;
            for (int i = 0; i < len / 2; i++) {
                nums[2 * i] = bak[sStart--];
                nums[2 * i + 1] = bak[bStart--];

            }
            // 处理len(small) - len (big)=1;
            if (len % 2 != 0) {
                nums[len - 1] = bak[0];
            }
        }
    }
}
